package xyz.vopen.leetcode.q85;

import java.util.Stack;

/**
 * {@link ElveXu}
 *
 * @author <a href="mailto:iskp.me@gmail.com">Elve.Xu</a>
 * @version ${project.version} - 2020-04-30.
 */
public class ElveXu {

  public static void main(String[] args) {

    char[][] temp = {
        {'0','1','0','1','0','1','0'},
        {'0','1','0','1','1','1','1'},
        {'0','0','1','1','1','1','0'},
        {'0','0','0','1','1','1','0'}
    };

    System.out.println(maximalRectangle(temp));

  }

  public static int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int[] height = new int[matrix[0].length];
    for (int i = 0; i < matrix[0].length; i++) {
      if (matrix[0][i] == '1') height[i] = 1;
    }
    int result = largestInLine(height);
    for (int i = 1; i < matrix.length; i++) {
      resultHeight(matrix, height, i);
      result = Math.max(result, largestInLine(height));
    }
    return result;
  }

  private static void resultHeight(char[][] matrix, int[] height, int index) {
    for (int i = 0; i < matrix[0].length; i++) {
      if (matrix[index][i] == '1') {
        height[i] += 1;
      } else {
        height[i] = 0;
      }
    }
  }

  private static int largestInLine(int[] height) {
    if (height == null || height.length == 0) return 0;
    int len = height.length;
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    for (int i = 0; i <= len; i++) {
      int h = (i == len ? 0 : height[i]);
      if (stack.isEmpty() || height[stack.peek()] <= h) {
        stack.push(i);
      } else {
        int top = stack.pop();
        int area = height[top] * (stack.isEmpty() ? i : i - 1 - stack.peek());
        maxArea = Math.max(maxArea, area);
        i--;
      }
    }
    return maxArea;
  }
}
